//二叉树先序遍历的迭代实现

class Solution
{
public:
    vector<int> res;

    vector<int> preorderTraversal(TreeNode *root)
    {
        preOrder(root);
        return res;
    }

    void preOrder(TreeNode *root)
    {
        stack<TreeNode *> node;

        while (root || !node.empty())
        {
            //先序遍历 先输出中间节点 再往左移 完了向右移
            while (root)
            {
                res.push_back(root->val);
                node.push(root);
                root = root->left;
            }

            if (!node.empty())
            {
                root = node.top();
                node.pop();
                root = root->right;
            }
        }
    }
};